/*
7-2 两个有序链表序列的合并（20 分）提问
	已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。

	输入格式:
	输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。

	输出格式:
	在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。

	输入样例:
	1 3 5 -1
	2 4 6 8 10 -1
	输出样例:
	1 2 3 4 5 6 8 10
*/
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
struct ListNode {
    int data;
    struct ListNode *next;
};

struct ListNode *createlist()
{
	ListNode *p = NULL, *q = NULL, *head = NULL;
	int temp;
	p = new ListNode;
	head = p;
	while(1)
	{
		scanf("%d", &temp);
		if(temp == -1)
			break;
		p->data = temp;
		q = p;
		p = new ListNode;
		q->next = p;
	}
	if(q == NULL)
		return NULL;
	q->next = NULL;
	free(p);
	return head;
}
struct ListNode *mergelists(struct ListNode *list1, struct ListNode *list2)
{
	struct ListNode *head = NULL, *temp;
	if(list1 == NULL)
		return list2;
	if(list2 == NULL)
		return list1;
	if(list1->data > list2->data)
	{
		head = list2;
		list2 = list2->next;
	}
	else
	{
		head = list1;
		list1 = list1->next;
	}
	temp = head;
	while(list1 != NULL && list2 != NULL)
	{
		if(list1->data > list2->data)
		{
			temp->next = list2;
			list2 = list2->next;
		}
		else
		{
			temp->next = list1;
			list1 = list1->next;
		}
		temp = temp->next;
	}
	if(list1 == NULL)
		temp->next = list2;
	else
		temp->next = list1;
	return head;
}
void printlist( struct ListNode *head )
{
     struct ListNode *p = head;
	 if(p==NULL)
	 {
		printf("NULL");
		return;
	 }
     while (p->next) {
           printf("%d ", p->data);
           p = p->next;
     }
	 printf("%d", p->data);
     printf("\n");
}

int main()
{
    struct ListNode  *list1, *list2;

    list1 = createlist();
    list2 = createlist();
    list1 = mergelists(list1, list2);
    printlist(list1);
	
    return 0;
}